package uestc.lj.basicPromotion.hash;

import java.util.HashMap;
import java.util.Random;

/**
 * 设计一种结构，包含插入、删除、等概率随即返回结构中的任何一个key
 * 并要求时间复杂度均为O(1)
 *
 * @Author:Crazlee
 * @Date:2021/11/25
 */
public class Code02_RandomPool {
	public static class RandomPool<K> {
		private HashMap<K, Integer> keyIndexMap;
		private HashMap<Integer, K> indexMap;
		private int size;

		public RandomPool() {
			this.keyIndexMap = new HashMap<>();
			this.indexMap = new HashMap<>();
			this.size = 0;
		}

		public void insert(K key) {
			if (!keyIndexMap.containsKey(key)) {
				keyIndexMap.put(key, size);
				indexMap.put(size++, key);
			}
		}

		public void delete(K key) {
			if (keyIndexMap.containsKey(key)) {
				int deleteIndex = keyIndexMap.get(key);
				int lastIndex = size--;
				K lastKey = indexMap.get(lastIndex);
				keyIndexMap.put(lastKey, deleteIndex);
				indexMap.put(deleteIndex, lastKey);
				keyIndexMap.remove(key);
				indexMap.remove(key);
			}
		}

		public K getRandom() {
			if (size == 0) {
				return null;
			}

			Random random = new Random();
			int randomIndex = random.nextInt(size);
			return indexMap.get(randomIndex);
		}
	}
}
